def lcs_length(X,Y):
    m=len(X)
    n=len(Y)
    c=[[0]*(n+1) for i in xrange(m+1)]
    b=[[None]*n for i in xrange(m)]
    for i in xrange(m):
        for j in xrange(n):
            if X[i]==Y[j]:
                c[i+1][j+1]=c[i][j]+1
                b[i][j]='7'
            elif c[i][j+1]>=c[i+1][j]:
                c[i+1][j+1]=c[i][j+1]
                b[i][j]='8'
            else:
                c[i+1][j+1]=c[i+1][j]
                b[i][j]='4'
    return c,b
def print_lcs(b,X,i,j):
    if i==-1 or j==-1:
        return
    if b[i][j]=='7':
        print_lcs(b,X,i-1,j-1),
        print X[i],
    elif b[i][j]=='8':
        print_lcs(b,X,i-1,j)
    else:
        print_lcs(b,X,i,j-1)
def do_print_lcs(b,X,Y):
    m=len(X)
    n=len(Y)
    print_lcs(b,X,m-1,n-1)

if __name__=='__main__':
    from pprint import pprint
    X='ABCBDAB'
    Y='BDCABA'
    print 'X:',X
    print 'Y:',Y
    c,b=lcs_length(X,Y)
    print 'c:'
    pprint(c)
    print 'b:'
    pprint(b)
    print 'LCS:',
    do_print_lcs(b,X,Y)
